/***尚硅谷Java数据结构与java算法                    ***/
/***https://www.bilibili.com/video/BV1E4411H73v   ***/
/***使用栈实现一个计算器，可实现多位数的加减运算      ***/
/***利用后缀表达式                                 ***/
/***C++ 实现版本    written by Daniel             ***/
#include <string>
#include <stack>
#include <list>
// C++的正则表达式库
#include <regex>
#include <iostream>
//调用其中的atoi函数
#include <cstdlib>
#include <memory>
using std::cout;
using std::endl;
using std::list;
using std::regex;
using std::shared_ptr;
using std::stack;
using std::string;
list<string> getList(string &expression);
int getResult(list<string> &list);
int operPriority(const string &oper);
list<string> expressToList(const string &expression);
list<string> transToSuffixExpress(const list<string> &strList);

int main(int argc, char **argv)
{
    string express("1+((2+3)*4)-5");
    list<string> expressList = expressToList(express);
    for (auto item : expressList)
    {
        cout << item << "\t";
        // cout<<"hello world!"<<endl;
    }
    cout << endl;
    list<string> suffixExpress = transToSuffixExpress(expressList);
    for (auto item : suffixExpress)
    {
        cout << item << "\t";
        // cout<<"hello world!"<<endl;
    }
    cout << endl;
    // //数字和符号用空格隔开
    // string expression("30 4 + 5 * 6 - ");
    // list<string> strList = getList(expression);
    // // for (auto str : strList)
    // // {
    // //     cout << str << endl;
    // // }
    int result = getResult(suffixExpress);
    cout << "final result=" << result << endl;
    // // cout<<"hello world!"<<endl;
    // system("pause");
    return 0;
}
//将中缀表达式的字符串  分解之后  存入一个列表中
list<string> expressToList(const string &expression)
{
    list<string> list;
    size_t index = 0;
    auto len = expression.length();
    string str = "";
    do
    {
        if (expression[index] < 48 || expression[index] > 57)
        {
            list.push_back(string(1, expression[index]));
            index++;
        }
        else
        {
            str = "";
            while ((expression[index] >= 48 && expression[index] <= 57) && index < len)
            {
                str.append(1, expression[index]);
                index++;
            }
            list.push_back(str);
        }
    } while (index < len);
    return list;
}
//将中缀表达式转换为后缀表达式
int operPriority(const string &oper)
{
    if (oper == "+" || oper == "-")
    {
        return 0;
    }
    else if (oper=="*"||oper=="/"){
        return 1;
    }
    return 2;
}

list<string> transToSuffixExpress(const list<string> &strList)
{
    stack<string> s1;
    list<string> retList;
    //匹配至少一个 0-9之间的数字，贪婪匹配；
    std::regex num_regex("//d+");
    //执行遍历操作
    for (auto item : strList)
    {
        do
        {
            //如果能匹配上数字，说明item是数字，直接加入retList；
            if (std::regex_match(item, num_regex))
            {
                retList.push_back(item);
                break;
            } //处理计算符号；
            if (s1.empty() || s1.top() == "(" || item == "(")
            {
                s1.push(item);
                break;
            } //优先级比栈顶元素高
            else if (operPriority(item) > operPriority(s1.top()))
            {
                s1.push(item);
                break;
            } //右边括号
            else if (item == ")")
            {
                while (s1.top() != "(")
                {
                    retList.push_back(s1.top());
                    s1.pop();
                } //去除左括号；
                s1.pop();
                break;
            }
            else
            {
                //将栈顶的元素弹出，压入retList中
                retList.push_back(s1.top());
                s1.pop();
                //需要重新将item和新的栈顶元素比较；
                continue;
            }
        } while (1);
    }
    while (!s1.empty())
    {
        retList.push_back(s1.top());
        s1.pop();
    }
    return retList;
}

list<string> getList(string &expression)
{
    string tempStr;
    int len = expression.length();
    list<string> strList;
    for (int i = 0; i < len; i++)
    {
        if (expression[i] == ' ')
        {
            strList.push_back(tempStr);
            tempStr.clear();
            continue;
        }
        tempStr.append(string(1, expression[i]));
    }
    return strList;
}

int getResult(list<string> &list)
{
    //利用栈这种数据结构，进行后缀表达式的计算
    //如果是遇到运算符，取出两个数，对这个标点进行计算
    stack<int> numStack;
    // int len = list.size();
    int num1 = 0, num2 = 0;
    int ret = 0;
    //使用正则表达式进行匹配，匹配不到0，需要改善
    std::regex num_regex("[0-9]\\d{0,8}");
    for (auto item : list)
    {
        //如果拿到的字符串是个整数，那么压栈
        if (std::regex_match(item, num_regex))
        {
            //压入的是数字
            numStack.push(atoi(item.c_str()));
        }
        //如果拿到的字符串是个标点，那么从栈中取出两个整数进行计算
        else
        {
            num1 = numStack.top();
            numStack.pop();
            num2 = numStack.top();
            numStack.pop();
            ret = 0;
            if (item == "*")
            {
                ret = num2 * num1;
            }
            else if (item == "/")
            {
                ret = num2 / num1;
            }
            else if (item == "+")
            {
                ret = num2 + num1;
            }
            else if (item == "-")
            {
                ret = num2 - num1;
            }
            else
            {
                cout << "符号输入有误" << endl;
            }
            numStack.push(ret);
        }
    }
    return numStack.top();
}
